# !/usr/bin/python
# -*- coding: utf-8 -*-

def shellSort(arr):
    import math
    gap = 1
    while(gap < len(arr)/3):
        gap = gap*3 + 1
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > temp:
                arr[j + gap] = arr[j]
                j -= gap
            arr[j + gap] = temp
        gap = math.floor(gap/3)
    return arr

if __name__ == '__main__':
    arr = [9,3,6,8,4,7]
    print(shellSort(arr))